1. Field of the Invention
The present invention generally relates to computer implemented graph drawing so as to exhibit the structure of the graph through the drawing on a standard-sized computer monitor and, more particularly, to computer implemented graph drawing which combines a force-directed approach with polynomial or quadratic approximation.
2. Description of the Prior Art
Many disciplines of science and engineering use graphs to represent systems comprised of a large number of interacting components, especially when the individual components are simple. Physicists and chemists rely on graphs to model interactions between many particles, as in the case of molecular structure. Electrical engineers use them to represent Very Large Scale Integrated (VLSI) circuits. The use of graphs is particularly important in computer science and information technology. Graphs are a natural representation for most databases and networks. Often, graphical visualizations of such systems reveal far more structure than textual ones, as per the cliche that a picture is worth a thousand words.
A person, however, needs a representation of the graph which is not only visual but readable. The conventional and intuitive way to represent a graph visually is to draw nodes as boxes and edges as line segments connecting the boxes. Even so, there are an infinite number of such drawings for any given graph, since the placement of boxes is arbitrary. Nonetheless, some drawings are more "aesthetic" than others.
Ideally, the aesthetic criteria would specify that the structure of a graph was evident to a human being. This definition, however, is so vague as to itself be an area of active research. Instead, practitioners of graph drawing accept various quantified criteria to establish the "cost" of a drawing and then seek to minimize this cost.
The graph drawing problem is that of arranging the nodes and edges of a combinatorial graph on a geometric space, such as the plane, so as to exhibit the structure of the graph through the drawing. Various existing approaches model the problem physically, treating the nodes as like-charged particles and the edges as springs, and then seeking to minimize the energy of the drawing. These approaches, generally classified as "force-directed," have three problems: speed, quality, and reliability.
In force-directed placement, there are two quantified criteria to minimize: (1) spring energy from the edges and (2) repulsion energy among all the nodes. The first models the edges as springs with an optimal rest length; when they are not at this rest length, they exert a force according to Hooke's Law. This length is either specified for each edge or assumed to be a constant for all edges. The second models the nodes as identically charged particles that repel each other according to Coulomb's Law.
The published algorithms for drawing general graphs (see, for example, G. Di Battista, P. Eades, R. Tamassia, and I. Tollis, "Algorithms for Drawing Graphs: an Annotated Bibliography," Computational Geometry: Theory and Applications 4:235-282, 1994) all use the spring/charge model described above, which was initially proposed by P. Eades in "A Heuristic for Graph Drawing", Congressus Numerantium 42:159-160, 1984. The principal algorithms in the field are those of T. Kamada and S. Kawai in "An Algorithm for Drawing General Undirected Graphs", Information Processing Letters 31:7-15, 1989, T. Fruchterman and E. Reingold in "Graph Drawing by Force-Directed Placement", Software-Practice and Experience 21 (no. 11):1129-1164, 1991, R. Davidson and D. Harel in "Drawing Graphs Nicely Using Simulated Annealing", Technical Report CS 89-13, Department of Applied Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot, 1989 (revised July 1993, to appear in Communications ACM), and D. Tunkelang in "A Practical Approach to Drawing Undirected Graphs", Technical Report CS-94-161, School of Computer Science, Carnegie Mellon University, 1994. The last two also assign a cost to edge crossings in the drawing which is linear in the number of crossings.